package shuati.shua;

public class EnergyNeededWithMonotonicStack {
    public static int minEnergyNeeded(int[] heights) {
        int n = heights.length - 1;
        int[] dp = new int[n + 1];

        dp[n] = Math.max(0, -heights[n]); // 从最后一个基地跳到终点，需要的最小能量

        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Math.max(0, dp[i + 1] - heights[i]); // 从当前基地跳到下一个基地的最小能量
        }

        return dp[0] + heights[0]; // 最终结果为从0号基地跳到1号基地需要的能量，再加上1号基地的高度

    }

    public static void main(String[] args) {
        int[] heights = {5, 8, 3, 6, 2, 7};
        int minEnergy = minEnergyNeeded(heights);
        System.out.println("最小能量值为: " + minEnergy);
    }
}
